Announcements

• Reading assessment 2 and Programming assignment 2 due today at 8pm on Gradescope.

• Quiz 1 during the Monday, February 5 discussion sections.

  • Content: The quiz covers Part 1 of the course. This includes all lectures up to Lecture 4, both discussion sections so far, and all reading and programming assignments through the end of this week (Week 3 in the course schedule).
  • Format: The quiz is in pencil-and-paper format; no calculators or notes are permitted. There will be 5 questions, and you need to meet the stated expectations on 4 of the 5 questions to pass the quiz.
  • Time: The quiz is intended to take 50 minutes, but you can stay longer (for students in the first discussion section) or begin earlier (for students in the second discussion section) if you'd like.

• Reading assessment 3 released today, due in 1 week on Thursday 2/8

• Programming assignment 3 released later today, due in 2 weeks on Thursday 2/15 (along with Programming assignment 4)

Lecture 5: From Cryptography to Cryptocurrencies

A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending.

– Satoshi Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System

Learning Outcomes

By the end of today's lecture, you will learn:

• How to make financial payments via cryptocurrencies.
• The role that hash functions and digital signatures play, and the extra technological and economic ideas that Bitcoin introduces on top of them.
• The blockchain data structure, and its role as a "public ledger" within a cryptocurrency.
• How Bitcoin achieves consensus and agreement on the state of the blockchain/public ledger, and three types of attacks that we must prevent miners from performing on Bitcoin.

5.1 Internet-based Money

⚠ Warning: The cryptocurrency market is incredibly volatile. Investing in cryptocurrencies is a bad way to make money, and a good way to lose money. Do not invest in cryptocurrencies!

With that warning stated: we're going to explore the world of cryptocurrencies in Part 2 of this class, for two reasons.

1. Cryptocurrencies build upon hash functions and digital signatures, and combine them in clever ways.
2. There are many lessons we can learn from the story of Internet-based money, which we will apply to other problems that require reaching agreement over the Internet. (We will return to this point in Part 3 of the course.)

Our starting point into cryptocurrencies is to build a digital version of a banking system, where people can transfer money to each other electronically over the Internet without the need for a single trusted banking authority.

Our digital money system should be "secure" against "powerful adversaries."

(We will make more precise today both the security requirements and the kinds of adversaries that we can withstand.)

Alice		Mallory		Bob
	$\longrightarrow$		$\longrightarrow$

In the physical world, when Bob receives a check from Alice, he may be suspicious that Alice is trying to deceive him. He needs to be able to verify the following three properties.

1. Alice properly signed the check

2. Alice possesses $1 in her bank account

3. Alice does not double spend the money by writing a check to someone else at the same time

For a digital monetary system:

• A digital signature scheme like RSA or ECDSA can satisfy objective #1, because signatures are unforgeable.
• To satisfy the other two objectives, it would help to have a digital version of a ledger that is available to everyone.

A ledger is a book or collection of accounts in which account transactions are recorded. Each account has an opening or carry-forward balance, and would record each transaction as either a debit or credit in separate columns, and the ending or closing balance.

For every debit recorded in a ledger, there must be a corresponding credit, so that the debits equal the credits in the grand totals.

Source: Wikipedia

Source: Wikipedia

Imagine for the moment that there was a book that is:

• Public, meaning that anyone can read it at any time.
• Append-only, meaning that:
  • Anyone can add new information at the end of the ledger, but
  • Nothing that is already in the ledger can ever be erased or overwritten.

If you had such a ledger, then you can emulate the bank!

5.2 Bitcoin's Public Ledger

Bitcoin is a public and peer-to-peer cryptocurrency. It is a digital coin, combined with a digital ledger that keeps track of how many Bitcoins each party holds at any moment in time.

Rather than relying on a bank, the Bitcoin ledger is maintained by everyone running the Bitcoin software. Anyone can run the Bitcoin software and store a copy of the ledger on their computer.

Bitcoin was invented in 2009 by an anonymous party (or parties) holding the pseudonym Satoshi Nakamato.

While we will focus today on financial transactions, in principle you can store any data on Bitcoin.

The first transaction on the Bitcoin blockchain encodes the following message: "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks". This message was in reference to an article posted in a British newspaper on January 3, 2009.

[Image source: https://en.bitcoin.it/]

Because the Bitcoin ledger is public, anyone can read any message that has ever been stored on the blockchain.

# This code connects to a bitcoin node (hosted on https://mempool.space) 
# holding the full bitcoin blockchain and extracts the first message
# encoded in the genesis block of the coinbase transaction. 

import requests
from binascii import unhexlify


# getting the block id for the genesis block (block 0).
genesis_block_id = requests.get('https://mempool.space/api/block-height/0').text

# getting all the block transactions of block 0 and parsing it
response = requests.get('https://mempool.space/api/block/' + genesis_block_id + '/txs')

# decode the special message in the genesis block
print(unhexlify(response.json()[0]['vin'][0]['scriptsig_asm'].split(" ")[5]).decode('ascii'))

The Times 03/Jan/2009 Chancellor on brink of second bailout for banks

Returning back to the topic of financial transactions: if you have a public ledger that is also append-only, then you could use it to:

1. Record every account and its current balance.
2. Record every financial transaction between two accounts.

In fact, you don't even need to do both! One can be inferred from the other.

1. The account model is what we are used to from the traditional banking system. In this approach, the bank maintains a list of every account and its current balance. When a transaction is submitted, the bank updates its record of accounts by debiting the sender and crediting the receiver.

2. Most cryptocurrencies work in the other direction: they store a public ledger containing every financial transaction ever made. This is called the unspent transaction output model, or UTXO.

In the UTXO model, for a transaction to be valid:

• The sender of the transaction must specify where they got their coins from.
• The sender shouldn't be sending more than what they have. What goes out must be less than or equal to what goes in. If $\textit{in} \ge \textit{out}$, then the difference $\textit{in}-\textit{out}$ is considered fees and a miner can claim this "leftover" money. Otherwise, the transaction is considered invalid.

[Image source: researchgate.net]

Or to think about it another way: the ledger records the movement of each individual coin in the system. Each coin is handed to the next person when its current owner produces a digital signature that publicly attests to the fact that the coin is being given to someone new.

Transactions in Bitcoin act slightly different than checks do in the physical world.

• They do not quite say "Alice hereby agrees to give 1 coin to Bob, signed Alice."
• Instead, they say "the person who holds the secret key corresponding to $\textit{pk}_{\textit{Alice}}$ hereby agrees to give 1 coin to the person who holds the secret key corresponding to public key $\textit{pk}_\textit{Bob}$, signed by the holder of $\textit{sk}_{\textit{Alice}}$."

[Image source: Nakamoto whitepaper]

5.3 The Blockchain

The data structure for Bitcoin's public ledger is called a blockchain. It is a sequence of blocks, which themselves contain several transactions.

If everyone acts honestly, the intention is that new blocks are only added to the end of the chain.

In more detail: a Bitcoin transaction is a single money transfer, just like a written check from a sender to a receiver. But unlike a check:

• There can be more than one sender or receiver.
• We write the sender and receiver's public keys, rather than their real-world identities. (One benefit here is that referring to everyone by these pseudonyms avoids the need for a PKI.)

• Transactions are irrevocable. If you make a mistake and send your money to the wrong place, it is gone forever!

  

(Note: transactions in Bitcoin are actually more complicated than just a digital signature; they can involve more sophisticated computer scripts. We will return to this point in a future lecture.)

The transactions are then grouped into blocks.

• Each block contains several transactions.
• A block is limited in size to around 2 megabytes, which is enough to store a few thousand transactions.
• A block is created within Bitcoin approximately every 10 minutes.

The blocks are linked together into a blockchain.

Every block references the hash of the previous block.

[Image source: Nakamoto whitepaper]

Example. Here is a screenshot of some blocks that were mined, or created, yesterday afternoon. There is also one partial block that is in the process of being formed.

[Source: mempool.space, at block 828285]

I took these screenshot using a blockchain explorer at the website mempool.space. But you don't have to trust this website; anyone can run a the Bitcoin software and join the peer-to-peer network to see these blocks and transactions as they appear.

As the screenshot shows, there are over 800,000 blocks in the Bitcoin network at the moment. Collectively, they hold almost 1 billion transactions.

The signatures in these transactions add up quickly in size! At the moment, the blockchain is around 545 GB in size. So anyone can download the ledger, but it might take you awhile to do so.

5.4 Participants in Bitcoin

The most important property of the Bitcoin blockchain is that all participants eventually reach agreement over the state of the ledger. If I believe that Alice owns 3 coins, then (eventually) so should you.

Agreement should be possible even if some of the participants are trying to tamper with or censor the ledger.

More specifically, we want a blockchain to achieve two types of agreement properties.

1. Liveness: Every honest transaction eventually makes it into some block.
2. Safety: The contents of each block are eventually agreed-upon by all honest participants in the Bitcoin network.

(Note the use of the word "eventually" in each claim. We'll come back to that in a bit, and discuss how long "eventually" might take.)

At a high level, there are three types of participants within Bitcoin.

• A light client only needs to hold one or more secret keys for a digital signature scheme. (And optionally also a small amount of additional data, which we will discuss next week.)

  We consider the corresponding public key also to be their bank account number. These accounts might have money, if (1) someone else has sent money to this account within some transaction in the past and (2) no subsequent transaction has spent the money.

• A node additionally stores the entire state of the blockchain. (Note: this can be large! The Bitcoin blockchain is currently about 545 gigabytes in size.)

• A miner additionally tries to write new blocks on the blockchain. (We will explore the role of miners in more detail today and next time.)

Anyone can create a Bitcoin account. All that is needed is a secret key and public key for a digital signature scheme like ECDSA or Schnorr signatures.

In the snippet of code below, we are creating an actual Bitcoin address right now! (But it has no money, since nobody has signed over their coins to us.)

## WARNING: This code is just for demonstration purposes.
## Do not execute this code to create a Bitcoin key in practice!
## This code does not ensure a safe place to store your secret key.

# !pip install "cryptos @ git+https://github.com/nicolas3355/cryptos"

from cryptos.keys import gen_secret_key, PublicKey
from cryptos.bitcoin import BITCOIN

# generate a secret/public key pair
secret_key = gen_secret_key(BITCOIN.gen.n)
public_key = PublicKey.from_sk(secret_key)
print('generated secret key, in hex format:')
print(hex(secret_key))
print('\ncorresponding public key, as an elliptic curve point:')
print(public_key)

# get the associated bitcoin address
addr = public_key.address(net='main', compressed=True)
print('\ncompressed bitcoin address, in base 58 check format:')
print(addr)

generated secret key, in hex format:
0xfe5ab33d89c05037913f0883816a899096e587b1f34129879121887263d6fe3

corresponding public key, as an elliptic curve point:
PublicKey(curve=Curve(p=115792089237316195423570985008687907853269984665640564039457584007908834671663, a=0, b=7), x=29285620428575169888252848216873123226713903519975304285337050457251827757408, y=60257316663837306241142736219388666767475129173325834536877913924619457724853)

compressed bitcoin address, in base 58 check format:
1z69QtZWYUMPaaD8EzW6HmTWDxHMsnvvH

Creating an account is easy. Keeping track of this account is a bit harder. If you accidentally delete your secret key, then you will never be able to spend the money in the account -- effectively, your money is gone forever.

We will discuss in a future lecture how we can make it easier for people to keep track of their secret key(s) in a secure way.

Mining a block is hard... and actually this is done on purpose.

Bitcoin needs miners: without them, no money transactions can ever be recorded.

So the Bitcoin system incentivizes people to become miners. If you create or mine a new block, then you get two kinds of rewards:

1. You get to create new coins out of thin air. Specifically, you get 6.25 Bitcoins, which is worth about $260,000 at current exchange rates. (This is the only way that new Bitcoins get introduced into circulation. In Bitcoin terminology, this is called a coinbase transaction.)

2. You receive the transaction fees that people set aside for you within their transactions.

For example, this picture shows some of the contents of block number 828285, which was created yesterday on the Bitcoin network.

If all miners act honestly, then the ecosystem works well: people can conduct money transfers over the Internet, and the miners receive a reward for their efforts.

5.5 Mining Attacks

But what if miners are dishonest? What could go wrong?

Just to state upfront:

A bad miner cannot directly create a new transaction to spend your money. Only you can do that, because it requires your secret signing key.

In more detail, thanks to existential unforgeability under a chosen message attack:

• If your money hasn't been spent, the miner cannot sign a message to transfer it to themselves.
• If your money has been spent, the miner cannot sign a new message to transfer it to themselves instead.

Recall that we will consider three categories of security concerns in this course.

• Confidentiality: keeping data or people's identities hidden from others.
• Integrity: preventing raw data or the data science results from being altered, or at least allowing for detection of tampering.
• Availability: ensuring that data science remains accessible and censorship-resistant.

Bitcoin doesn't provide any confidentiality guarantees: the whole world knows how much money is in each account. Furthermore, even though people don't write their names on the ledger, it is often possible for an adversary Mallory to link an account to a real-world identity. (More on this later.)

Instead, Bitcoin provides integrity and availability.

Question. Suppose you are a miner and have the power to write blocks on the Bitcoin blockchain. How could you potentially abuse this power to harm integrity and availability?

Here are 3 types of attacks that a malicious miner could perform. (Note: this is not an exhaustive list; there are other possible attacks too.)

• Censorship: The miner can refuse to post certain transactions. This would break our goal of allowing anyone to append new information to the end of the book.

• Inconsistency: The miner can send different states of the blockchain to different nodes. This would break our goal of having a global ledger that anyone can read.

• Double spending: The miner could go back in time and rewrite an earlier block. This would break our goal that the ledger is append-only.

[Image source: Bitcoin wiki]

As an example, suppose that Mallory pays Alice and subsequently Alice pays Carol. If a miner deletes the Mallory-to-Alice transaction, then the later transaction becomes invalid as well because Alice no longer has any money to spend.

Even worse, if Mallory is the miner, then Mallory could post a new transaction that pays the money to another account under her own control... perhaps her friend Bob, or perhaps another account held by herself. In this way, Mallory could reclaim her previously-spent money to spend again in the future.

Thwarting mining attacks

Cryptocurrencies like Bitcoin have been carefully designed to ensure that censorship, inconsistency, and double spending attacks are practically infeasible to perform.

(Note: Bitcoin's protections against these 3 attacks are actually related, but for the purposes of this class, we will treat them separately.)